
;;; Basic functions, macros

;; Block
(set do (macro args `((fn () ,@args))))

;; Make list
(set list (fn args args))

;; Define function
(set def (macro (name parms . body)
           `(set ,name (fn ,parms ,@body))))

;; Define macro
(set mac (macro (name parms . body)
           `(set ,name (macro ,parms ,@body))))

;; cxxr
(def caar   (xs) (car (car xs)))
(def cadr   (xs) (car (cdr xs)))
(def cddr   (xs) (cdr (cdr xs)))
(def caddr  (xs) (car (cddr xs)))
(def cdddr  (xs) (cdr (cddr xs)))
(def cadddr (xs) (car (cdddr xs)))
(def cddddr (xs) (cdr (cdddr xs)))

;; not
(def no (x) (is x nil))
(def isnt (x y) (no (is x y)))

;; is x equal type y?
(def isa (x y) (is (type x) y))

;; list with cons last
(def list* ls
  (if (no (cdr ls))
      (car ls)
    (cons (car ls) (apply list* (cdr ls)))))

;; cons cell?
(def acons (x) (consp x))
;; atom?
(def atom (x) (no (consp x)))

;; identity function
(def idfn (x) x)

;; Map for 1 list.
(def map1 (f xs)
  (if (no xs)
      nil
    (cons (f (car xs)) (map1 f (cdr xs)))))

;; Make pair from list: (a b c d ...) => ((a b) (c d) ...)
(def pair (xs)
  (if (no xs)
      nil
    (no (cdr xs))
      (list (list (car xs)))
    (cons (list (car xs) (cadr xs))
          (pair (cddr xs)))))

;; Is All element not nil? Then return last element
(mac and args
  (if args
      (if (cdr args)
          `(if ,(car args) (and ,@(cdr args)))
        (car args))
    't))

;; Find from association list
(def assoc (key al)
  (if (atom al)
      nil
    (and (acons (car al)) (is (caar al) key))
      (car al)
    (assoc key (cdr al))))

(def alref (al key) (cadr (assoc key al)))

;; Bind multi variable (let in Lisp)
(mac with (parms . body)
  `((fn ,(map1 car (pair parms))
        ,@body)
    ,@(map1 cadr (pair parms))))

;; Bind 1 variable (let1 in Scheme)
;(mac let (var val . body)
;  `(with (,var ,val) ,@body))
(mac let (var val . body)
  (if (acons var)
      `(apply (fn ,var ,@body) ,val)
    `(with (,var ,val) ,@body)))

;; let*
(mac withs (parms . body)
  (if (no parms) 
      `(do ,@body)
    `(let ,(car parms) ,(cadr parms) 
       (withs ,(cddr parms) ,@body))))


;;; Reader macro

;; [...] = (fn (_) ...)
(set-macro-character #\[
                     (fn (strm ch)
                         (let body (read-delimited-list #\] strm)
                           `(fn (_) ,body))))
;(set-macro-character #\]
;                     (get-macro-character #\)))

;; Complement function
(set-macro-character #\~
                     (fn (strm ch)
                         (let f (read strm)
                           `(fn args (no (apply ,f args))))))


; Need rfn for use in macro expansions.

;; Define recursive function
(mac rfn (name parms . body)
  `(let ,name nil
     (set ,name (fn ,parms ,@body))))

;; Define recursive function, bind to 'self
(mac afn (parms . body)
  `(let self nil
     (set self (fn ,parms ,@body))))

; Ac expands x:y:z into (compose x y z), ~x into (complement x)

; Only used when the call to compose doesn't occur in functional position.  
; Composes in functional position are transformed away by ac.

(mac compose args
  (let g (uniq)
    `(fn ,g
       ,((afn (fs)
           (if (cdr fs)
               (list (car fs) (self (cdr fs)))
               `(apply ,(if (car fs) (car fs) 'idfn) ,g)))
         args))))

;; if f then nil else t
(mac complement (f)
  (let g (uniq)
    `(fn ,g (no (apply ,f ,g)))))

;; Reverse list (no side effect)
(def rev (xs) 
  ((afn (xs acc)
     (if (no xs)
         acc
         (self (cdr xs) (cons (car xs) acc))))
   xs nil))


;; With uniq symbol
(mac w/uniq (names . body)
     (if (acons names)
         `(with ,(apply append (map1 (fn (n) (list n '(uniq)))
                                     names))
            ,@body)
       `(let ,names (uniq) ,@body)))

(mac or args
  (and args
       (w/uniq g
         `(let ,g ,(car args)
            (if ,g ,g (or ,@(cdr args)))))))

;; List or nil?
(def alist (x) (or (no x) (consp x)))

(mac in (x . choices)
  (w/uniq g
    `(let ,g ,x
       (or ,@(map1 (fn (c) `(is ,g ,c)) choices)))))

; should take n args

(def iso (x y)
  (or (is x y)
      (and (acons x)
           (acons y)
           (iso (car x) (car y))
           (iso (cdr x) (cdr y)))))

(mac when (test . body)
  `(if ,test (do ,@body)))

(mac unless (test . body)
  `(if (no ,test) (do ,@body)))

#|
(mac while (test . body)
  (w/uniq (gf gp)
    `((rfn ,gf (,gp)
        (when ,gp ,@body (,gf ,test)))
      ,test)))
|#
(mac while (test . body)
  (w/uniq (gf)
    `((rfn ,gf ()
        (when ,test ,@body (,gf))))))

(def empty (seq)
  (or (no seq)
      (and (no (acons seq)) (is (len seq) 0))))

(def reclist (f xs)
  (and xs (or (f xs) (reclist f (cdr xs)))))


(def testify (x)
  (if (isa x 'fn) x [is _ x]))

(def some (test seq)
  (let f (testify test)
    (if (alist seq)
        (reclist (compose f car) seq)
      (recstring f:seq seq))))

(def all (test seq) 
  (~some (complement (testify test)) seq))

(def mem (test seq)
  (let f (testify test)
    (reclist [if (f:car _) _] seq)))

(def find (test seq)
  (let f (testify test)
    (if (alist seq)
        (reclist   [if (f:car _) (car _)] seq)
        (recstring [if (f:seq _) (seq _)] seq))))

; Possible to write map without map1, but makes News 3x slower.

;(def map (f . seqs)
;  (if (some1 no seqs)
;       nil
;      (no (cdr seqs))
;       (let s1 (car seqs)
;         (cons (f (car s1))
;               (map f (cdr s1))))
;      (cons (apply f (map car seqs))
;            (apply map f (map cdr seqs)))))

(def map (f . seqs)
  (if (some [isa _ 'string] seqs)
      (withs (n   (apply min (map len seqs))
              new (newstring n))
        ((afn (i)
           (if (is i n)
               new
             (do (sref new (apply f (map [_ i] seqs)) i)
               (self (+ i 1)))))
         0))
    (no (cdr seqs))
      (map1 f (car seqs))
    ((afn (seqs)
       (if (some no seqs)
           nil
         (cons (apply f (map1 car seqs))
               (self (map1 cdr seqs)))))
     seqs)))

(def mappend (f . args)
  (apply append (apply map f args)))  ; + nil => append

(def firstn (n xs)
  (if (no xs)
      xs
    (and (> n 0) xs)
      (cons (car xs) (firstn (- n 1) (cdr xs)))))

(def nthcdr (n xs)
  (if (no n)  xs
      (> n 0) (nthcdr (- n 1) (cdr xs))
              xs))

; Generalization of pair: (tuples x) = (pair x)

(def tuples (xs . args)  ; (o n 2)
  (let n (if (no args) 2 (car args))
    (if (no xs)
        nil
      (cons (firstn n xs)
            (tuples (nthcdr n xs) n)))))

(def caris (x val) 
  (and (acons x) (is (car x) val)))



(def atomic-invoke (f)
  (f))

(mac atomic body
  `(atomic-invoke (fn () ,@body)))

(mac atlet args
  `(atomic (let ,@args)))
  
(mac atwith args
  `(atomic (with ,@args)))

(mac atwiths args
  `(atomic (withs ,@args)))





; Would like to write a faster case based on table generated by a macro,
; but can't insert objects into expansions in Mzscheme.

(mac caselet (var expr . args)
  (let ex (afn (args)
            (if (no (cdr args)) 
                args
              `((is ,var ',(car args))
                ,(cadr args)
                ,@(self (cddr args)))))
    `(let ,var ,expr (if ,@(ex args)))))

(mac case (expr . args)
  `(caselet ,(uniq) ,expr ,@args))




(def ref (obj i)
  (case (type obj)
    cons   (cons-ref obj i)
    string (string-ref obj i)
    table  (gethash i obj)
    ))

(def cons-ref (s i)
  (if (no s)  (error "index error")
      (> i 0) (cons-ref (cdr s) (- i 1))
    (car s)))

(def sref (obj val ind)
  (case (type obj)
    cons (scar (nthcdr ind obj) val)
    table (sethash ind obj val)
    ))


; setforms returns (vars get set) for a place based on car of an expr
;  vars is a list of gensyms alternating with expressions whose vals they
;   should be bound to, suitable for use as first arg to withs
;  get is an expression returning the current value in the place
;  set is an expression representing a function of one argument
;   that stores a new value in the place

; A bit gross that it works based on the *name* in the car, but maybe
; wrong to worry.  Macros live in expression land.

; seems meaningful to e.g. (push 1 (pop x)) if (car x) is a cons.
; can't in cl though.  could I define a setter for push or pop?

(set setter (table))

(mac defset (name parms . body)
  (w/uniq gexpr
    `(sref setter
           (fn (,gexpr)
             (let ,parms (cdr ,gexpr)
               ,@body))
           ',name)))

(defset car (x)
  (w/uniq g
    (list (list g x)
          `(car ,g)
          `(fn (val) (scar ,g val)))))

(defset cdr (x)
  (w/uniq g
    (list (list g x)
          `(cdr ,g)
          `(fn (val) (scdr ,g val)))))

(defset caar (x)
  (w/uniq g
    (list (list g x)
          `(caar ,g)
          `(fn (val) (scar (car ,g) val)))))

(defset cadr (x)
  (w/uniq g
    (list (list g x)
          `(cadr ,g)
          `(fn (val) (scar (cdr ,g) val)))))

(defset cddr (x)
  (w/uniq g
    (list (list g x)
          `(cddr ,g)
          `(fn (val) (scdr (cdr ,g) val)))))




(def ssyntax (x) nil)

; Note: if expr0 macroexpands into any expression whose car doesn't
; have a setter, setforms assumes it's a data structure in functional 
; position.  Such bugs will be seen only when the code is executed, when 
; sref complains it can't set a reference to a function.

(def setforms (expr0)
  (let expr (macex expr0)
    (if (isa expr 'sym)
         (if (ssyntax expr)
             (setforms (ssexpand expr))
             (w/uniq (g h)
               (list (list g expr) 
                     g
                     `(fn (,h) (set ,expr ,h)))))
        ; make it also work for uncompressed calls to compose
        (and (acons expr) (metafn (car expr)))
         (setforms (expand-metafn-call (ssexpand (car expr)) (cdr expr)))
         (let f (ref setter (car expr))
           (if f
               (f expr)
               ; assumed to be data structure in fn position
               (do (when (caris (car expr) 'fn)
                     (warn "Inverting what looks like a function call" 
                           expr0 expr))
                   (w/uniq (g h)
                     (let argsyms (map [uniq] (cdr expr))
                        (list (+ (list g (car expr))
                                 (mappend list argsyms (cdr expr)))
                              `(,g ,@argsyms)
                              `(fn (,h) (sref ,g ,h ,@argsyms)))))))))))

(def metafn (x)
  (or (ssyntax x)
      (and (acons x) (in (car x) 'compose 'complement))))

(def expand-metafn-call (f args)
  (if (is (car f) 'compose)
      ((afn (fs)
         (if (caris (car fs) 'compose)            ; nested compose
              (self (join (cdr (car fs)) (cdr fs)))
             (cdr fs)
              (list (car fs) (self (cdr fs)))
             (cons (car fs) args)))
       (cdr f))
      (err "Can't invert " (cons f args))))

(def expand= (place val)
  (if (and (isa place 'sym) (~ssyntax place))
      `(set ,place ,val)
;      (let (vars prev setter) (setforms place)
      (withs (plc (setforms place)
              vars (car plc)
              prev (cadr plc)
              setter (caddr plc))
        (w/uniq g
          `(atwith ,(append vars (list g val))
             (,setter ,g))))))

(def expand=list (terms)
  `(do ,@(map (fn (args) (with (p (car args) v (cadr args)) (expand= p v)))  ; [apply expand= _]
              (pair terms))))

(mac = args
  (expand=list args))




;; diff: original Arc occur error when you give a dotted list, but here doesn't occur.
(def len (ls)
  ((afn (ls l)
     (if (acons ls)
         (self (cdr ls) (+ l 1))
       l))
   ls 0))




(mac loop (start test update . body)
  (w/uniq (gfn gparm)
    `(do ,start
       ((rfn ,gfn ()
          (when ,test
            (do ,@body ,update (,gfn))))
        ))))

;; diff: original Arc is include max, here is not include
(mac for (v init max . body)
  (w/uniq (gi gm)
    `(with (,v nil ,gi ,init ,gm ,max)
       (loop (set ,v ,gi) (< ,v ,gm) (set ,v (+ ,v 1))
         ,@body))))

(mac repeat (n . body)
  `(for ,(uniq) 0 ,n ,@body))

; could bind index instead of gensym

(mac each (var expr . body)
  (w/uniq (gseq g)
    `(let ,gseq ,expr
       (if (alist ,gseq)
           ((afn (,g)
              (when (acons ,g)
                (let ,var (car ,g) ,@body)
                (self (cdr ,g))))
            ,gseq)
#|
           (isa ,gseq 'table)
            (maptable (fn (,g ,var) ,@body)
                      ,gseq)
            (for ,g 0 (len ,gseq)
              (let ,var (,gseq ,g) ,@body))))))
|#
         ))))



(mac ontable (k v h . body)
  `(maptable (fn (,k ,v) ,@body) ,h))

(mac whilet (var test . body)
  (w/uniq (gf gp)
    `((rfn ,gf (,gp)
        (let ,var ,gp
          (when ,var ,@body (,gf ,test))))
      ,test)))

;; last pair of list
;; diff: original Arc occur error when give dotted-list, but here doesn't.
(def last (ls)
  (if (atom ls)
      ls
    ((afn (ls)
       (let d (cdr ls)
         (if (atom d)
             ls
           (self d))))
     ls)))

;; remove
(def rem (test seq)
  (let f (testify test)
    (if (alist seq)
        ((afn (s)
           (if (no s)       nil
               (f (car s))  (self (cdr s))
                            (cons (car s) (self (cdr s)))))
         seq)
      ;(coerce (rem test (coerce seq 'cons)) 'string))))
      )))

;; remove if not
(def keep (test seq)
  (rem (complement (testify test)) seq))

(def trues (f seq)
  (rem nil (map f seq)))

(mac do1 args
  (w/uniq g
    `(let ,g ,(car args)
       ,@(cdr args)
       ,g)))




(mac push (x place)
  (w/uniq gx
    (let (binds val setter) (setforms place)
      `(let ,gx ,x
         (atwiths ,binds
           (,setter (cons ,gx ,val)))))))

(mac swap (place1 place2)
  (w/uniq (g1 g2)
;    (with ((binds1 val1 setter1) (setforms place1)
;           (binds2 val2 setter2) (setforms place2))
    (let (binds1 val1 setter1) (setforms place1)
      (let (binds2 val2 setter2) (setforms place2)
        `(atwiths ,(append binds1 (list g1 val1) binds2 (list g2 val2))
           (,setter1 ,g2)
           (,setter2 ,g1))))))

(mac rotate places
  (with (vars (map [uniq] places)
         forms (map setforms places))
    `(atwiths ,(mappend (fn (g args)
                          (let (binds val setter) args
                            (append binds (list g val))))
                        vars
                        forms)
       ,@(map (fn (g args)
                (let (binds val setter) args
                  (list setter g)))
              (append (cdr vars) (list (car vars)))
              forms))))

(mac pop (place)
  (w/uniq g
    (let (binds val setter) (setforms place)
      `(atwiths ,(append binds (list g val))
         (do1 (car ,g) 
              (,setter (cdr ,g)))))))

(def adjoin (x xs . args)
  (let test (if (no args) iso (car args))
    (if (some [test x _] xs)
        xs
      (cons x xs))))

(mac pushnew (x place . args)
  (w/uniq gx
    (let (binds val setter) (setforms place)
      `(atwiths ,(+ (list gx x) binds)
         (,setter (adjoin ,gx ,val ,@args))))))

(mac pull (test place)
  (w/uniq g
    (let (binds val setter) (setforms place)
      `(atwiths ,(+ (list g test) binds)
         (,setter (rem ,g ,val))))))

(mac ++ (place . args)
  (let i (if (no args) 1 (car args))
    (if (isa place 'sym)
        `(= ,place (+ ,place ,i))
      (w/uniq gi
        (let (binds val setter) (setforms place)
          `(atwiths ,(+ binds (list gi i))
             (,setter (+ ,val ,gi))))))))

(mac -- (place . args)
  (let i (if (no args) 1 (car args))
    (if (isa place 'sym)
        `(= ,place (- ,place ,i))
      (w/uniq gi
        (let (binds val setter) (setforms place)
          `(atwiths ,(+ binds (list gi i))
             (,setter (- ,val ,gi))))))))




(def pr args
  (map1 disp args)
  (car args))

(def prn args
  (do1
   (apply pr args)
   (pr "\n")))

(mac iflet (var expr then . rest)
  (w/uniq gv
    `(let ,gv ,expr
       (if ,gv (let ,var ,gv ,then) ,@rest))))

(mac whenlet (var expr . body)
  `(iflet ,var ,expr (do ,@body)))

(mac aif (expr . body)
  `(let it ,expr
     (if it
         ,@(if (cddr body)
               `(,(car body) (aif ,@(cdr body)))
             body))))

(mac awhen (expr . body)
  `(let it ,expr (if it (do ,@body))))

(mac aand args
  (if (no args)
      't 
    (no (cdr args))
      (car args)
    `(let it ,(car args) (and it (aand ,@(cdr args))))))

(mac accum (accfn . body)
  (w/uniq gacc
    `(withs (,gacc nil ,accfn [push _ ,gacc])
       ,@body
       ,gacc)))





(def string args
  (apply string-append (map [coerce _ 'string] args)))



(def even (n) (is (mod n 2) 0))

(def odd (n) (no (even n)))







(mac forlen (var s . body)
  `(for ,var 0 (len ,s) ,@body))

(mac on (var s . body)
  (if (is var 'index)
      (err "Can't use index as first arg to on.")
      (w/uniq gs
        `(let ,gs ,s
           (forlen index ,gs
             (let ,var (ref ,gs index)
               ,@body))))))

(def best (f seq)
  (if (no seq)
      nil
      (let wins (car seq)
        (each elt (cdr seq)
          (if (f elt wins) (= wins elt)))
        wins)))
              
(def max args (best > args))
(def min args (best < args))

; (mac max2 (x y)
;   (w/uniq (a b)
;     `(with (,a ,x ,b ,y) (if (> ,a ,b) ,a ,b))))

(def most (f seq) 
  (unless (no seq)
    (withs (wins (car seq) topscore (f wins))
      (each elt (cdr seq)
        (let score (f elt)
          (if (> score topscore) (= wins elt topscore score))))
      wins)))



(def copy (x . args)
  (let x2 (case (type x)
            sym    x
            cons   (apply (fn args args) x)
;            string (let new (newstring (len x))
;                     (forlen i x
;                       (= (new i) (x i)))
;                     new)
;            table  (let new (table)
;                     (ontable k v x 
;                       (= (new k) v))
;                     new)
                   (err "Can't copy " x))
    (map (fn (args) (with (k (car args) v (cadr args))
                      (= x2 (car v))))  ;(= (x2 k) v)))
         (pair args))
    x2))

(def abs (n)
  (if (< n 0) (- n) n))

; The problem with returning a list instead of multiple values is that
; you can't act as if the fn didn't return multiple vals in cases where
; you only want the first.  Not a big problem.

(def round (n)
  (withs (base (trunc n) rem (abs (- n base)))
    (if (> rem 1/2) ((if (> n 0) + -) base 1)
        (< rem 1/2) base
        (odd base)  ((if (> n 0) + -) base 1)
                    base)))

(def roundup (n)
  (withs (base (trunc n) rem (abs (- n base)))
    (if (>= rem 1/2) 
        ((if (> n 0) + -) base 1)
        base)))

(def to-nearest (n quantum)
  (* (roundup (/ n quantum)) quantum))

(def avg (ns) (/ (apply + ns) (len ns)))

; Use mergesort on assumption that mostly sorting mostly sorted lists
; benchmark: (let td (n-of 10000 (rand 100)) (time (sort < td)) 1) 

(def sort (test seq)
  (if (alist seq)
      (mergesort test (copy seq))
      (coerce (mergesort test (coerce seq 'cons)) (type seq))))

; Destructive stable merge-sort, adapted from slib and improved 
; by Eli Barzilay for MzLib; re-written in Arc.

(def mergesort (less? lst)
  (with (n (len lst))
    (if (<= n 1) lst
        ; ; check if the list is already sorted
        ; ; (which can be a common case, eg, directory lists).
        ; (let loop ([last (car lst)] [next (cdr lst)])
        ;   (or (null? next)
        ;       (and (not (less? (car next) last))
        ;            (loop (car next) (cdr next)))))
        ; lst
        ((afn (n)
           (if (> n 2)
                ; needs to evaluate L->R
                (withs (j (/ (if (even n) n (- n 1)) 2) ; faster than round
                        a (self j)
                        b (self (- n j)))
                  (merge less? a b))
               ; the following case just inlines the length 2 case,
               ; it can be removed (and use the above case for n>1)
               ; and the code still works, except a little slower
               (is n 2)
                (with (x (car lst) y (cadr lst) p lst)
                  (= lst (cddr lst))
                  (when (less? y x) (scar p y) (scar (cdr p) x))
                  (scdr (cdr p) nil)
                  p)
               (is n 1)
                (with (p lst)
                  (= lst (cdr lst))
                  (scdr p nil)
                  p)
               nil))
         n))))

; Also by Eli.

(def merge (less? x y)
  (if (no x) y
      (no y) x
      (let lup nil
        (set lup
             (fn (r x y r-x?) ; r-x? for optimization -- is r connected to x?
               (if (less? (car y) (car x))
                 (do (if r-x? (scdr r y))
                     (if (cdr y) (lup y x (cdr y) nil) (scdr y x)))
                 ; (car x) <= (car y)
                 (do (if (no r-x?) (scdr r x))
                     (if (cdr x) (lup x (cdr x) y t) (scdr x y))))))
        (if (less? (car y) (car x))
          (do (if (cdr y) (lup y x (cdr y) nil) (scdr y x))
              y)
          ; (car x) <= (car y)
          (do (if (cdr x) (lup x (cdr x) y t) (scdr x y))
              x)))))








(def single (x) (and (acons x) (no (cdr x))))




(def reduce (f xs)
  (if (no xs)
      (apply f xs)
    ((afn (v rest)
          (if (no rest)
              v
            (self (f v (car rest)) (cdr rest))))
     (car xs) (cdr xs))))

(def rreduce (f xs)
  (if (or (no xs) (no (cdr xs)))
      (apply f xs)
    ((afn (rest)
          (if (no (cdr rest))
              (car rest)
            (f (car rest) (self (cdr rest)))))
     xs)))
